package leet;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author fance
 * @date 18-5-10 上午7:10
 */
public class BackTracking {

    /**
     * 46. 全排列
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 1) {
            return res;
        }
        permuteCore(nums,0,res);
        return res;
    }
    private void permuteCore(int[] nums, int index, List<List<Integer>> res) {
        if (index == nums.length - 1) {
            List<Integer> tmpList = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                tmpList.add(nums[i]);
            }
            res.add(tmpList);
        } else if (index < nums.length - 1) {
            for (int i = index; i < nums.length; i++) {
                int tmp = nums[i];
                nums[i] = nums[index];
                nums[index] = tmp;

                permuteCore(nums, index + 1, res);

                tmp = nums[i];
                nums[i] = nums[index];
                nums[index] = tmp;
            }
        }
    }


    /**
     * 78. 子集
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtrackForSubsets(res,new ArrayList<>(), nums,0);
        return res;
    }
    private void backtrackForSubsets(List<List<Integer>> res, List<Integer> tmpList,int[] nums, int start) {
        res.add(new ArrayList<>(tmpList));
        for (int i = start; i < nums.length; i++) {
            tmpList.add(nums[i]);
            backtrackForSubsets(res,tmpList,nums,i + 1);
            tmpList.remove(tmpList.size() - 1);
        }
    }


    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtrackForSubsets(res,new ArrayList<>(), nums,0);
        return res;
    }
    private void backtrackForSubsetsWithDup(List<List<Integer>> res, List<Integer> tmpList,int[] nums, int start) {
        res.add(new ArrayList<>(tmpList));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            tmpList.add(nums[i]);
            backtrackForSubsetsWithDup(res,tmpList,nums,i + 1);
            tmpList.remove(tmpList.size() - 1);
        }
    }


    public List<List<Integer>> permuteII(int[] nums){
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtrackForpermuteII(res,new ArrayList<>(), nums);
        return res;
    }
    private void backtrackForpermuteII(List<List<Integer>> res, List<Integer> tmpList, int [] nums) {
        if (tmpList.size() == nums.length) {
            res.add(new ArrayList<>(tmpList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (tmpList.contains(nums[i])) {
                    continue;
                }
                tmpList.add(nums[i]);
                backtrackForpermuteII(res,tmpList,nums);
                tmpList.remove(tmpList.size() - 1);
            }
        }
    }

     public List<List<Integer>> permuteIIWithDup(int[] nums){
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
         backtrackForpermuteIIWithDup(res,new ArrayList<>(), nums,new boolean[nums.length]);
        return res;
    }
    private void backtrackForpermuteIIWithDup(List<List<Integer>> res, List<Integer> tmpList,
                                              int [] nums, boolean[] used) {
        if (tmpList.size() == nums.length) {
            res.add(new ArrayList<>(tmpList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                    continue;
                }
                used[i] = true;
                tmpList.add(nums[i]);
                backtrackForpermuteIIWithDup(res,tmpList,nums,used);
                used[i] = false;
                tmpList.remove(tmpList.size() - 1);
            }
        }
    }


    public List<List<Integer>> combinationSum(int[] nums,int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtrackForcombinationSum(res,new ArrayList<>(), nums,target,0);
        return res;
    }
    private void backtrackForcombinationSum(List<List<Integer>> res,
                                            List<Integer> tmpList,
                                            int[] nums,
                                            int remain,
                                            int start) {
        if (remain < 0) {
            return;
        } else if (remain == 0) {
            res.add(new ArrayList<>(tmpList));
        } else {
            for (int i = start; i < nums.length; i++) {
                tmpList.add(nums[i]);
                backtrackForcombinationSum(res,tmpList,nums,remain - nums[i],i);
                tmpList.remove(tmpList.size() - 1);
            }
        }

    }

    public List<List<Integer>> combinationSumII(int[] nums,int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtrackForcombinationSumII(res,new ArrayList<>(),new boolean[nums.length], nums,target,0);
        return res;
    }
    private void backtrackForcombinationSumII(List<List<Integer>> res,
                                            List<Integer> tmpList,
                                            boolean[] used,
                                            int[] nums,
                                            int remain,
                                            int start) {
        if (remain < 0) {
            return;
        } else if (remain == 0) {
            res.add(new ArrayList<>(tmpList));
        } else {
            for (int i = start; i < nums.length; i++) {
                if ((i > start && nums[i] == nums[i - 1]) || used[i]) {
                    continue;
                }
                used[i] = true;
                tmpList.add(nums[i]);
                backtrackForcombinationSum(res,tmpList,nums,remain - nums[i],i + 1);
                tmpList.remove(tmpList.size() - 1);
                used[i] = false;
            }
        }

    }


    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtrackForPartition(res, new ArrayList<>(), s, 0);
        return res;
    }
    private void backtrackForPartition(List<List<String>> res,
                                       List<String> tmpList,
                                       String s,
                                       int start) {
        if (start == s.length()) {
            res.add(new ArrayList<>(tmpList));
        } else {
            for (int i = start; i < s.length(); i++) {
                if (isPalindrome(s,start,i)) {
                    tmpList.add(s.substring(start,i + 1));
                    backtrackForPartition(res,tmpList,s,i + 1);
                    tmpList.remove(tmpList.size() - 1);
                }
            }
        }
    }
    private boolean isPalindrome(String s, int lo, int hi) {
        while (lo < hi) {
            if (s.charAt(lo++) != s.charAt(hi--)) {
                return false;
            }
        }
        return true;
    }
    @Test
    public void test() {
        int[] nums = {1,2,2,3,3};
        // List<List<Integer>> res = permute(nums);
        List<List<Integer>> res = combinationSumII(nums,3);
        for (List<Integer> tmp : res) {
            for (Integer n : tmp) {
                System.out.print(n + ",");
            }
            System.out.println();
        }
    }
}
